import type { Heap as HeapType } from "../types";

/**
 * #### 比较两个元素的大小关系的枚举
 */
export enum Compare {
  /**
   * 小于
   */
  LESS_THAN = -1,
  /**
   * 大于
   */
  BIGGER_THAN = 1,
  /**
   * 等于
   */
  EQUALS = 0,
}

/**
 * #### 比较两个元素的大小关系的函数接口
 */
export interface CompareFun<T> {
  (a: T, b: T): Compare;
}

/**
 * #### 默认的比较函数，用于比较两个元素的大小关系
 * @param a 元素a
 * @param b 元素b
 * @returns -1 | 0 | 1
 */
export function defaultCompareFun<T>(a: T, b: T): Compare {
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

/**
 * #### 堆抽象类
 */
abstract class Heap<T> implements HeapType<T> {
  // 定义一个数组heap，用于存储堆中的元素
  heap: Array<T>;
  // 定义一个比较函数compareFun，用于比较两个元素的大小关系
  protected compareFun: CompareFun<T>;
  // 构造函数，接收一个比较函数compareFun，默认为defaultCompareFun
  constructor(compareFun: CompareFun<T> = defaultCompareFun) {
    this.compareFun = compareFun;
    this.heap = [];
  }
  // 获取左子节点的索引
  protected static getLeftIndex(index: number) {
    return index * 2 + 1;
  }
  // 获取右子节点的索引
  protected static getRightIndex(index: number) {
    return index * 2 + 2;
  }
  // 获取父节点的索引
  protected static getParentIndex(index: number) {
    return index === 0 ? void 0 : Math.floor((index - 1) / 2);
  }
  // 交换两个元素的值
  static swap<T>(arr: Array<T>, index1: number, index2: number) {
    [arr[index1], arr[index2]] = [arr[index2], arr[index1]];
  }
  // 抽象方法，用于插入元素
  abstract insert(value: T): boolean;
  // 抽象方法，用于提取元素
  abstract extract(): T | undefined;
  // 获取堆顶元素
  find() {
    return this.isEmpty() ? void 0 : this.heap[0];
  }
  // 获取堆的大小
  size() {
    return this.heap.length;
  }
  // 判断堆是否为空
  isEmpty(): boolean {
    return this.heap.length === 0;
  }
  // 清空堆
  clear(): void {
    this.heap = [];
  }
  // 将堆转换为字符串
  toString() {
    return this.heap.toString();
  }
}

// 导出Heap类
export default Heap;
